
def count_substring_matches(s, w):
    i = j = 0
    matches = 0
    while i <= len(s) - len(w) or j > 0:
        if j == len(w):
            matches += 1
            i -= (j - 1)
            j = 0
        else:
            if s[i] == w[j]:
                i += 1
                j += 1
            else:
                i -= (j - 1)
                j = 0

    return matches

def fast_count_substring_matches(s, w, t):
    i = j = 0
    matches = 0
    while True:
        if j == len(w):
            # check for match
            matches += 1
            j = t[j-1]
        if i == len(s):
            # reached the end
            return matches
        if s[i] == w[j]:
            # so far so good, on to the next one
            i += 1
            j += 1
        else:
            # no match, backtrack in w if we're not at the beginning
            # already, else advance in s.
            if j == 0:
                i += 1
            else:
                j = t[j-1]

def compute_backtrack_array(w):
    t = [0 for _ in range(len(w))]
    t[0] = 0
    for i in range(1, len(t)):
        backtrack = t[i-1]
        while True:
            if w[backtrack] == w[i]:
                t[i] = backtrack + 1
                break
            elif backtrack == 0:
                break
            else:
                backtrack = t[backtrack]

    return t


if __name__ == "__main__":
    s = "ABCBBBAAABCABABCABCCACCCAABBCABCC"
    w = "CC"

    print(count_substring_matches(s, w))

    s = "abababcabacababcababab"
    w = "ababcabab"

    t = compute_backtrack_array(w)
    print(t)

    print(fast_count_substring_matches(s,w,t))